package com.weave.heap;

import com.weave.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * 二叉堆（最大堆）
 * @author MJ Lee
 *
 * @param <E>
 */
@SuppressWarnings("unchecked")
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {
	private E[] elements;
	private static final int DEFAULT_CAPACITY = 10;

	public BinaryHeap(){
		this(null,null);
	}
	public BinaryHeap(E[] elements){
		this(elements,null);
	}
	public BinaryHeap(Comparator<E> comparator){
		this(null,comparator);
	}
	public BinaryHeap(E[] elements, Comparator<E> comparator){
		super(comparator);
		if(elements == null || elements.length ==0){
			this.elements = (E[]) new Object[DEFAULT_CAPACITY];
		}else{
			size = elements.length;
			int capacity = Math.max(elements.length,DEFAULT_CAPACITY);
			this.elements = (E[]) new Object[capacity];
			System.arraycopy(elements, 0, this.elements, 0, elements.length);
			heapify();
		}
	}

	@Override
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}

	@Override
	public void add(E element) {
		elementNotNullCheck(element);
		ensureCapacity(size + 1);
		elements[size++] = element;
		siftUp(size -1);
	}

	/**
	 * 获取堆顶元素
	 * @return
	 */
	@Override
	public E get() {
		emptyCheck();
		return elements[0];
	}

	/**
	 * 删除堆顶元素
	 * @return
	 */
	@Override
	public E remove() {
		emptyCheck();

		int lastIndex = --size;
		E root = elements[0];
		elements[0] = elements[lastIndex];
		elements[lastIndex] = null;

		siftDown(0);
		return root;
	}

	/**
	 * 取代堆顶元素，然后进行重新建堆，下滤操作
	 * @param element
	 * @return
	 */
	@Override
	public E replace(E element) {
		elementNotNullCheck(element);

		E root = null;
		if(size == 0){
			elements[0] = element;
			size++;
		}else{
			root = elements[0];
			elements[0] = element;
			siftDown(0);
		}
		return root;
	}

	private void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}

	private void emptyCheck() {
		if (size == 0) {
			throw new IndexOutOfBoundsException("Heap is empty");
		}
	}

	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) {
			return;
		}

		// 新容量为旧容量的1.5倍
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
	}

	private void heapify() {
		// 自上而下的上滤
		for (int i = 0; i < size; i++) {
			siftUp(i);
		}

		for (int i = (size>>1) - 1; i >=  0; i--) {
			siftDown(i);
		}
	}

	/**
	 * 让index位置的元素上滤
	 * 也就是子结点与父结点比较
	 * @param index
	 */
	private void siftUp(int index){
		E element = elements[index];
		while(index >0){
			int parentIndex = (index - 1) >> 1;
			E parent = elements[parentIndex];
			if(compare(element,parent) <= 0){
				break;
			}
			elements[index] = parent;

			index = parentIndex;
		}
		elements[index] = element;
	}

	/**
	 * 让index位置的元素下滤
	 * 也就是父结点与子结点比较
	 * @param index
	 */
	private void siftDown(int index){
		E element = elements[index];
		int half = size >> 1;
		/*
			父结点与子结点比较,所以index位置必须是非叶子结点
			第一个叶子节点的索引 == 非叶子节点的数量
			index < 第一个叶子节点的索引
		 */
		while (index < half){
			// 默认左结点
			int childIndex = (index << 1) +1;
			E child = elements[childIndex];
			int rightChildIndex = childIndex +1;

			if(rightChildIndex < size && compare(elements[rightChildIndex],child) >0){
				childIndex = rightChildIndex;
				child = elements[childIndex];
			}
			if(compare(element,child) >= 0){
				break;
			}

			elements[index] = child;
			index = childIndex;
		}
		elements[index] = element;
	}



	@Override
	public Object root() {
		return 0;
	}

	@Override
	public Object left(Object node) {
		int index = ((int)node << 1) + 1;
		return index >= size ? null : index;
	}

	@Override
	public Object right(Object node) {
		int index = ((int)node << 1) + 2;
		return index >= size ? null : index;
	}

	@Override
	public Object string(Object node) {
		return elements[(int)node];
	}
}
